package FourthWeek;

public class Thursday {
    //240、搜索二维矩阵II
    public boolean searchMatrix(int[][] matrix, int target) {
        //二分查找
        //对其二维数组的每一个一维数组进行二分查找
        for (int[] row : matrix) {
            int index = searchIndex(row,target);
            if (index >= 0) {
                return true;
            }
        }
        return false;
    }

    private int searchIndex(int[] row, int target) {
        int left = 0,right = row.length - 1;
        while(left < right) {
            int mid = left + (right - left + 1) / 2;
            if (row[mid] <= target) {
                left = mid;
            }else {
                right = mid - 1;
            }
        }
        if (row[left] == target) {
            return left;
        }else {
            return -1;
        }
    }

    public boolean searchMatrix1(int[][] matrix, int target) {
        //暴力枚举
        for (int[] row : matrix) {
            for (int i = 0;i < row.length;i++) {
                if (row[i] == target) {
                    return true;
                }
            }
        }
        return false;
    }


    //222、完全二叉树的节点个数
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int leftNodes = countNodes(root.left);
        int rightNodes = countNodes(root.right);

        return leftNodes + rightNodes + 1;
    }

    //167、两数之和II - 输入有序数组
    public int[] twoSum(int[] numbers, int target) {
        //双指针
        int left = 0,right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum > target) {
                right--;
            } else if (sum < target) {
                left++;
            }else {
                return new int[]{left + 1,right + 1};
            }
        }
        return new int[]{-1,-1};
    }

    public int[] twoSum1(int[] numbers, int target) {
        //二分查找
        //从左往右开始固定一个数字，对其剩余的进行二分查找操作
        for (int i = 0;i < numbers.length;i++) {
            int left = i + 1,right = numbers.length - 1;//这里把left固定一个数字
            while(left < right) {
                int mid = left + (right - left + 1) / 2;
                if (numbers[mid] <= target - numbers[i]) {
                    left = mid;
                }else {
                    right = mid - 1;
                }
            }
            if (numbers[left] == target - numbers[i]) {
                return new int[]{i + 1,left + 1};
            }
        }
        return new int[]{-1,-1};
    }

    //154、寻找旋转排序数组中的最小值II
    public int findMin(int[] nums) {
        //我们这里的mid值和right位置的值进行比较进行，因为我们的right就是在翻转数组后相对较小的数值，当right往左移动的时候
        //right值还在进行减小，我们对其进行比较，并且因为这里的数据还会出现相等的值
        //所以当mid和right相等的时候呢，我们就不知道是mid值是在最小值的左侧还是右侧，所以我们把right进行-1
        int left = 0,right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                //在第一段位置，这里没有我们要找的数据，我们的left要争取跳出这个区间
                left = mid + 1;
            }else if (nums[mid] < nums[right]){
                right = mid;
            }else {
                right--;
            }
        }

        return nums[left];
    }
}
